This invention relates to a syndrome computing apparatus used for error correcting apparatuses using cyclic codes.
At present, error correcting apparatuses with cyclic codes are utilized for communication devices, data memories, and so on. These error correcting apparatuses makes computation of syndromes on data (codewords) previously encoded by utilizing a generator polynominal. The error correcting apparatuses are adapted to detect data error positions by utilizing that all but xe2x80x9c0xe2x80x9d of the syndrome results from an error caused through a transmission line, which corresponds to an error position in a one-to-one manner.
The data as codewords used for computation is obtainable, through double error-correctable BCH (Bose-Chaudhuri-Hocquenghem) encoding, by expressing for example a generator polynominal G(x) using the following two polynomials g1(x) and g2(x).
g1(x)=x5+x2+1
g2(x)=x5+x4+x3+x2+1
where g1(x) is a primitive polynominal and g2(x) is a minimal polynominal having a solution xcex13 thereto provided that xcex1 is a solution to g1(x). These polynominals are given based on the elements of a Galois field GF(25xe2x88x921).
The below computation is a modulo-2 arithmetic that uses, as a factor, an element of Galois field GF(2).
Here, the generator polynominal G(x) is expressed as:
G(x)=g1(x)g2(x)=x10+x9+x8+x6+x5+x3+1.
As for the data, information bits (i20, i19, i18, . . . , i0) representative of 21-bit actual information is given by:
I(X)=i20x30+i19x29+i18x28+ . . . +i0x10.
This equation is divided by the generator polynominal G(x) to obtain a residue (p9, p8, p7, . . . , p0). This residue is added as check bits to the information bits.
That is, if encoded data is given by W=(w30, w29, w28, . . . , w0), the following relationship is obtained:
(w30, w29, w28, . . . , w0)=(i20, i19, i18, . . . , i0, p9, p8, p7, . . . , p0)
This gives a residue 0 when it is divided by G(x).
This data can be expressed by a polynominal as:
W(X)=w30x30+w29x29+w28x28+ . . . +w0x0
where W(X) has roots of xcex1 and xcex13. That is, those fallen onto W(xcex1)=W(xcex13)=0 are included in a set for this code.
From the above, those having W(xcex1) and W(xcex13) not fallen onto 0 will not constitute the above code, resulting in involving an error. This value is referred to as a syndrome (S). Data errors are specified of position and corrected by examining this value.
If the syndrome is vector-represented as S=(s1, s2) (s1 and s2 are respectively correspond to xcex1 and xcex13 and the solution xcex13 of g2(x) is written by xcex2, the syndrome can be determined by matrix operation as follows:
S=Wxc2x7HT
where H is a check matrix expressed by   H  =      [                                                      α              30                        ,                          α              29                        ,                          α              28                        ,            …            ⁢                          xe2x80x83                        ,                          α              2                        ,                          α              1                        ,                          α              0                                                                                                                             β              30                        ,                          β              29                        ,                          β              28                        ,            …            ⁢                          xe2x80x83                        ,                          β              2                        ,                          β              1                        ,                          β              0                                            ]  
As stated above, it has been a conventional practice to compute a syndrome directly from the data inputted. However, where the data is unclear of position at which data begins, it is impossible to correctly compute a syndrome.
To this end, where collating for a frame synchronous pattern, etc. that is unclear of position data (codewords) begins, the data has to be collated over the entire portions thereof such that it is determined whether or not it resides within an error correctable range where the number of the error bits can be warranted by the code.
It is therefore the object of the invention to provide a syndrome computing means which is capable of computing a syndrome at every 1-bit input even where a codeword is unclear of position at which it begins, by computing a first syndrome on input data and simultaneously a second syndrome on the data with a delay by a number of bits due to previous fetch into a delay means, and vector-adding modulo 2 the first syndrome without delay to the second syndrome at every 1-bit input.
According to the present invention, a syndrome computing apparatus, comprises: a first syndrome computing means for receiving a predetermined number of bits of data (codewords) encoded based on a predetermined generator polynominal, and performing a syndrome computation on the data inputted based on the generator polynominal; a delay means for outputting the data with a delay by the predetermined number of bits; a second syndrome computing means for receiving the data delayed by the predetermined number of bits, and performing a syndrome computation on the data inputted based on the generator polynominal; and an operating means for vector-adding modulo 2 a first syndrome outputted by the first syndrome computing means to a second syndrome outputted by the second syndrome computing means, whereby an output of the operating means is offered as a syndrome based on the generator polynominal.
Preferably, the first and second syndrome computing means are formed by a combination of an exclusive-OR circuit and registers, the delay means being configured by a shift register with the predetermined number of the bits of the codewords, and the operating means is configured by an exclusive-OR circuit.
According to one form of the present invention, a syndrome computing apparatus, comprises: a plurality of first syndrome computing means for receiving a predetermined number of bits of data encoded based on a generator polynominal, and performing a syndrome computation on the inputted data by using an individually assigned polynominal among a plurality of polynominals constituting the generator polynominal; a delay means for outputting the data with a delay by the predetermined number of bits; a plurality of second syndrome computing means for receiving the data delayed by the predetermined number of bits from the delay means, and performing a syndrome computation on the inputted data by using an individually assigned polynominal among a plurality of polynominals constituting the generator polynominal; a plurality of operating means for vector-adding modulo 2, using the individually assigned polynominal among the plurality of polynominals constituting the generator polynominal, a first syndrome to a second syndrome which are respectively outputted by the first syndrome computing means, the second syndrome computing means corresponding to the individually assigned polynominal; whereby an output of the operating means is offered as a syndrome based on the generator polynominal.